package com.leetcode.partition3;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/2/16 12:26
 */
public class LC218天际线问题 {

    private static final int N = 20010;
    private static Set<Integer> set = new TreeSet<>();
    private static Map<Integer, Integer> map = new HashMap<>(N << 1);
    private static Node[] tr = new Node[N * 4];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] buildings = new int[n][3];
        for (int i = 0; i < n; i++) {
            String[] ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            buildings[i] = new int[]{a, b, c};
        }
        writer.write(getSkyline(buildings) + "\n");
        writer.flush();
    }

    public static List<List<Integer>> getSkyline(int[][] buildings) {
        //有序离散化
        for (int[] building : buildings) {
            set.add(building[0]);
            set.add(building[1]);
        }
        int cnt = 0;
        for (int coord : set) map.put(coord, ++cnt);
        //创建线段树，维护一个区间最大值
        build(1, 1, (set.size() << 1) + 10);
        for (int[] building : buildings) {
            int l = map.get(building[0]), r = map.get(building[1]), val = building[2];
            //这里的右区间少一个单位，让他作为下一个的起点
            modify(1, l, r - 1, val);
        }
        List<List<Integer>> answer = new ArrayList<>();
        cnt = 1;
        for (int x : set) {
            int res = query(1, cnt, cnt);
            if (answer.size() == 0 || answer.get(answer.size() - 1).get(1) != res) answer.add(Arrays.asList(x, res));
            cnt++;
        }
        return answer;
    }

    private static int query(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u].maxh;
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        if (l > mid) return query(u << 1 | 1, l, r);
        return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }

    private static void pushup(int u) {
        tr[u].maxh = max(tr[u << 1].maxh, tr[u << 1 | 1].maxh);
    }

    private static void pushdown(int u) {
        if (tr[u].flag != 0) {
            int left = u << 1, right = u << 1 | 1;
            tr[left].flag = max(tr[left].flag, tr[u].flag);
            tr[right].flag = max(tr[right].flag, tr[u].flag);
            tr[left].maxh = max(tr[left].maxh, tr[left].flag);
            tr[right].maxh = max(tr[right].maxh, tr[right].flag);
            tr[u].flag = 0;
        }
    }

    private static void modify(int u, int l, int r, int h) {
        if (l <= tr[u].l && r >= tr[u].r) {
            tr[u].maxh = max(tr[u].maxh, h);
            tr[u].flag = max(tr[u].flag, h);
        } else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) modify(u << 1, l, r, h);
            if (r > mid) modify(u << 1 | 1, l, r, h);
            pushup(u);
        }
    }

    private static void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l != r) {
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    private static int max(int a, int b) {
        return Math.max(a, b);
    }

    private static class Node {
        private int l, r;
        private int maxh, flag;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }

        public Node(int l, int r, int maxh, int flag) {
            this.l = l;
            this.r = r;
            this.maxh = maxh;
            this.flag = flag;
        }
    }
}
